package linkedlist;


import java.util.Stack;

public class SingleLinkedListDeme{
    public static void main(String[] args) {
        //进行测试
        //先创建节点
        HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode hero2 = new HeroNode(21, "卢俊义", "玉麒麟");
        HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
        HeroNode hero4 = new HeroNode(44, "林冲", "豹子头");
        HeroNode hero5 = new HeroNode(29, "AAA", "aaa");
        HeroNode hero6 = new HeroNode(21, "BBB", "bbb");
        HeroNode hero7 = new HeroNode(79, "CCC", "ccc");
        HeroNode hero8 = new HeroNode(28, "DDD", "ddd");

        //创建链表
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        SingleLinkedList singleLinkedList1 = new SingleLinkedList();
//        //加入
        singleLinkedList.add(hero1);
        singleLinkedList.add(hero2);
        singleLinkedList.add(hero3);
        singleLinkedList.add(hero4);
        singleLinkedList1.add(hero5);
        singleLinkedList1.add(hero6);
        singleLinkedList1.add(hero7);
        singleLinkedList1.add(hero8);
        SingleLinkedList.reversePrintTwo(singleLinkedList.getHead(),singleLinkedList1.getHead());
//        singleLinkedList.addByOrder(hero1);
//        singleLinkedList.addByOrder(hero4);
//        singleLinkedList.addByOrder(hero3);
//        singleLinkedList.addByOrder(hero2);
//
//        System.out.println("排序");
//        singleLinkedList1.list();
////        HeroNode hero5 = new HeroNode(2, "AAAA", "BBBB");
////        singleLinkedList.update(hero5);
////        System.out.println("更新");
////        singleLinkedList.list();
//////        singleLinkedList.delete(2);
//////        System.out.println("删除");
//////        singleLinkedList.list();
////        System.out.println(SingleLinkedList.getLength(singleLinkedList.getHead()));
////        System.out.println(SingleLinkedList.findLastIndexNode(singleLinkedList.getHead(),2));
////        SingleLinkedList.reverseList(singleLinkedList.getHead());
////        System.out.println("反转");
//        singleLinkedList.list();
//        System.out.println("调用Stack反转");
//        SingleLinkedList.reversePrint(singleLinkedList.getHead());

    }


}


//定义SingleLinkedList来管理英雄
class SingleLinkedList{
    //先初始化头结点，头结点不要动
    private HeroNode head = new HeroNode(0,"","");

    public HeroNode getHead() {
        return head;
    }

    public void setHead(HeroNode head) {
        this.head = head;
    }

    public void add(HeroNode heroNode){
        //当不考虑编号顺序时，找到当前链表的最后节点，将最后节点指向新的节点
        //因为head节点不能动，因此我们需要一个辅助节点temp
        HeroNode temp = head;
        while (true){
            //遍历链表，找到最后
            //找到链表的最后
            if (temp.next == null){
                break;
            }
            //没有找到的话，就继续往后找
            temp = temp.next;
        }
        //退出while循环时，temp指向最后链表的节点
        temp.next = heroNode;
    }
    public void addByOrder(HeroNode heroNode){
        //因为头结点不能动，因此仍然通过辅助变量
        //因为单链表，我们找到的temp是位于添加位置的前一个节点，否则插入失败
        HeroNode temp = head;
        boolean flag = false;//标志添加的符号是否存在，默认为false
        while (true){
            if (temp.next==null){//说明在链表最后
                break;//
            }
            if (temp.next.no > heroNode.no){//位置找到，就在temp的后面插入
                break;
            }else if(temp.next.no == heroNode.no){//序号已存在
                flag = true;
                break;
            }
            temp = temp.next;
        }
        //判断flag的值
        if (flag){
            System.out.printf("编号已存在，不能加入%s",heroNode.no);
        }else {
            heroNode.next = temp.next;
            temp.next = heroNode;
        }
    }

    //修改节点信息，根据编号修改
    public void update(HeroNode newHeroNode){
        //判断链表是否为空
        HeroNode temp = head;
        boolean flag = false;
        //找到需要修改的节点，根据no编号
        while (true){
            if (temp.next == null){
                System.out.println("找不到这个节点");
                break;
            }else if (temp.next.no == newHeroNode.no){
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag){
            temp.next.name = newHeroNode.name;
            temp.next.nickName = newHeroNode.nickName;
        }

    }

    //删除节点
    public void delete(int no){
        HeroNode temp = head;
        boolean flag = false;//是否找到待删除的节点
        while (true){
            if (temp.next == null){//已经到链表的最后
                break;
            }
            if (temp.next.no == no){//找到了待删除节点的前一个节点
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            temp.next = temp.next.next;
        }else {
            System.out.println("没找到要删除的节点");
        }
    }


    //显示链表
    public void list(){
        if (head.next == null){
            System.out.println("链表为空");
            return;
        }
        //因为头结点不能动，因此我们需要一个辅助变量来遍历
        HeroNode temp = head.next;
        while (true){
            //判断链表是否为空
            if (temp == null){
                break;
            }
            //输出节点信息
            System.out.println(temp);
            //将next后移
            temp = temp.next;
        }

    }
    //获取单链表的有效节点个数(如果带头结点，需要不统计头结点)

    /**
     * @param head 是链表的头结点
     * @return 返回的是有效节点的个数
     */
    public static int getLength(HeroNode head){
        if (head == null){//空链表
            return 0;
        }
        int length = 0;
        //定义辅助变量
        HeroNode cur = head.next;//从头结点后边统计
        while (cur != null){
            length++;
            cur = cur.next;
        }
        return length;
    }

    //查找单链表中单数第k个节点【新浪面试题】
    /**
     * 思路：
     * 1.编写一个方法，接受head节点，同时接受index
     * 2.index表示倒数index个节点
     * 3.先把链表从头到尾遍历一遍，得到链表总的长度
     * 4.得到长度后从链表第一个开始遍历，index重新计算 size - index
     * 5.
     *如果找到了，返回该节点，否则返回空
     */
    public static HeroNode findLastIndexNode(HeroNode head,int index){
        if (head.next == null) {//为空不遍历
            return null;
        }
        int length = getLength(head);
        //第二次遍历
        if (index <= 0||index > length){
            return null;
        }
        index = length - index;
        HeroNode temp = head.next;
        for (int i = 1; i <= index ; i++){
            temp = temp.next;
        }
        return temp;
    }
    /**
     * 单链表反转【腾讯面试题】
     * 参考思路
     * 1.先去定义新的节点reverseHead = new HeroNode()
     * 2.从头到尾遍历原来的链表，没遍历一个节点，就将其取出，并放在新的链表的最前端
     * 3.原来的链表的head.next=reverseHead.next
     */
    public static void reverseList(HeroNode head){
        //如果当前节点没有或者只有一个节点，就无须反转
        if (head.next == null|| head.next.next==null){
            return;
        }
        //定义辅助变量
        HeroNode cur = head.next;
        HeroNode next = null;//指向当前节点的下一个节点
        HeroNode reverseHead = new HeroNode(0, "", "");
        //开始遍历原来的链表
        while (cur != null){
            next = cur.next;//保存当前节点的下一个节点
            cur.next = reverseHead.next; //将cur的当前的节点指向新的链表的头部
            reverseHead.next = cur;
            cur = next;//让cur后移
        }//将head。next指向reverseList。next
        head.next = reverseHead.next;

    }
//    public static void reverseLinkedList(HeroNode head){
//        if (head.next == null){
//            System.out.println("节点为空");
//            return;
//        }
//        HeroNode reverseHead = new HeroNode(0, "", "");
//        HeroNode temp = head;
//        while (temp.next != null){
//
//            if (reverseHead.next == null){
//                reverseHead.next = temp.next;
//
//            } else {
//                HeroNode test1 = reverseHead.next;
//                HeroNode test2 = temp.next;
//                reverseHead.next = test2;
//                test2.next=test1;
//            }
//            temp = temp.next;
//        }
//        while (reverseHead.next != null){
//            System.out.println(reverseHead);
//            reverseHead = reverseHead.next;
//        }
//    }

    public static void reversePrint(HeroNode head){
        if (head.next == null || head.next.next==null){
            return;
        }

        Stack<HeroNode> s = new Stack<HeroNode>();
        while (head.next!=null){
            s.add(head.next);
            head = head.next;
        }
        while (!s.isEmpty()){
            System.out.println(s.pop());
        }
    }

    public static void reversePrintTwo(HeroNode node1,HeroNode node2){
        HeroNode temp = node1;
        HeroNode newHead = new HeroNode(0,"","");
        newHead.next = temp.next;
        while (true){
            if (temp.next == null){
                temp.next = node2.next;
                break;
            }
            temp = temp.next;
        }
        int size = getLength(node1) + getLength(node2);
        newHead = newHead.next;
        Stack<HeroNode> stack = new Stack<HeroNode>();
        while (newHead != null){
            stack.add(newHead);
            newHead = newHead.next;
        }
        HeroNode[] array = new HeroNode[stack.size()];
        int index = 0;
        while (!stack.isEmpty()){
            array[index] = stack.pop();
            index++;
        }
        for (int i=0;i<array.length;i++){
            for (int j=0;j<array.length-1;j++){
                if (array[i].no<array[j].no){
                    HeroNode t = array[i];
                    array[i] = array[j];
                    array[j] = t;
                }
            }
        }
        for (HeroNode h:array){
            System.out.println(h);
        }
    }
}


//定义HeroNode，每个HeroNode对象就是一个节点
class HeroNode {
    public int no;
    public String name;
    public String nickName;
    public HeroNode next;//指向下一个节点

    public HeroNode(int no, String name, String nickName) {
        this.no = no;
        this.name = name;
        this.nickName = nickName;
    }



    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickName='" + nickName + '\'' +
                '}';
    }
}
